//package a2025_02_19;
// 数组的第k大元素
// 使用分治快排的思想
//import java.util.Random;
//
//class Solution {
//    public int findKthLargest(int[] nums, int k) {
//        dfs(nums,0,nums.length-1,k);
//        return nums[nums.length-k];
//    }
//    public void dfs(int[] nums,int left,int right,int k){
//        if(right<=left) return;
//
//        int mid=nums[new Random().nextInt(right-left+1)+left];
//        int l=left-1;
//        int r=right+1;
//        int i=left;
//        while(i<r){
//            if(nums[i]<mid) swap(nums,++l,i++);
//            else if(nums[i]>mid) swap(nums,--r,i);
//            else i++;
//        }
//        int a=l-left+1;
//        int b=r-l-1;
//        int c=right-r+1;
//
//        if(c>=k) dfs(nums,r,right,k);
//        else if(b+c>=k) return;
//        else dfs(nums,left,l,k-b-c);
//    }
//    public void swap(int[] nums,int i,int j){
//        int temp=nums[i];
//        nums[i]=nums[j];
//        nums[j]=temp;
//    }
//}
